import numpy as np

cimport cython
cimport numpy as np

cdef class PySudoku(object):
    cdef readonly unsigned int w, h, size, tries
    cdef np.ndarray grid, solved
    def __init__(self, grid, int w=3, int h=3):
        assert w>0 and h>0 and len(grid) == w*h and len(grid[0]) == w*h
        self.w, self.h = w, h
        self.size = w * h
        self.grid = np.array(grid, dtype=np.uint8)
        self.tries = 0
        self.solved = self.__solve(self.grid)

    @cython.boundscheck(False)
    cdef np.ndarray __solve(self, np.ndarray grid):
        cdef bint found = True
        cdef unsigned int row, col, n, m, cand, lowest, lR, lC, blRl, blCl, blRr, blCr
        cdef np.ndarray candidates
        cdef np.ndarray newGrid
        while found and 0 in grid:
            while found and 0 in grid:
                found = False
                candidates = np.zeros((self.size, self.size, self.size), dtype=np.uint8)
                for row in xrange(self.size):
                    blRl = row // self.h * self.h
                    blRr = blRl + self.h
                    for col in xrange(self.size):
                        if grid[row, col] == 0:
                            blCl = col // self.w * self.w
                            blCr = blCl + self.w
                            for n in xrange(1, self.size + 1):
                                if (n not in grid[row] and
                                    n not in grid[:, col] and
                                    n not in grid[blRl : blRr, blCl : blCr]
                                    ): candidates[row, col, n-1] = n
                            cand = (candidates[row, col] > 0).sum()
                            if cand == 1:
                                grid[row, col] = candidates[row, col].max()
                                found = True
                            elif cand == 0:
                                raise ValueError("Bad grid: no candidates in"
                                                " cell [%i, %i]" % (row, col))
                                                
            if 0 in grid:
                for row in xrange(self.size):
                    blRl = row // self.h * self.h
                    for col in xrange(self.size):
                        if grid[row, col] == 0:
                            blCl = col // self.w * self.w
                            for n in candidates[row, col]:
                                if n != 0:
                                    cand = 0
                                    for m in xrange(self.size):
                                        if n in candidates[row, m]: cand += 1
                                        if n in candidates[m, col]: cand += 1
                                        if n in candidates[
                                            m % self.w + blRl,
                                            m // self.h + blCl]:
                                            cand += 1
                                        if cand > 1: break
                                    else:
                                        grid[row, col] = n
                                        found = True
                                        
        if 0 in grid: #dead point start guessing
            lowest = 100000
            for row in xrange(self.size):
                blRl = row // self.h * self.h
                blRr = blRl + self.h
                for col in xrange(self.size):
                    if grid[row, col] == 0:
                        blCl = col // self.w * self.w
                        blCr = blCl + self.w
                        n = (candidates[row, col] > 0).sum() + (grid[row, :] == 0).sum() + \
                            (grid[:, col] == 0).sum() + (grid[blRl : blRr, blCl : blCr] == 0).sum()
                        if n < lowest: lowest, lR, lC = n, row, col
            for cand in candidates[lR, lC]:
                if cand != 0:
                    self.tries += 1
                    newGrid = grid.copy()
                    newGrid[lR, lC] = cand
                    try: return self.__solve(newGrid)
                    except ValueError: pass #wrong guess
        else: return grid

    def __str__(self):
        box = self.size * self.h
        l = (self.w * 2 + 1)
        crosses = ("-" * l + "+") * (self.h - 1) + "-" * l
        dashes = ("-" * l * self.h)
        sep = "|\n|%s|\n| " % crosses
        row = ["\n+-%s-+\n| " % dashes]
        for i, n in enumerate(self.solved.flat):
            if i % box == 0:
                if i: row.append(sep)
            elif i % self.size == 0: row.append("|\n| ")
            elif i % self.w == 0: row.append("| ")
            row.append(n and "%i " % n or '  ')
        row.append("|\n+-%s-+\n" % dashes)
        return ''.join(row)

    def __repr__(self):
        return "<PySudoku instance %ix%i at %s>" % (self.size, self.size, hex(id(self)))
